package cn.bellychang.leetcode.question021;

/**
 * @author ChangLiang
 * @date 2021/3/7
 */
public class Solution4 {

    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {

        ListNode head = l1;
        ListNode temp = l2;
        while(temp!=null){
            l2 = l2.next;
            ListNode curr = head;
            ListNode prev = null;
            while(curr!=null && temp.val > curr.val){
                prev = curr;
                curr = curr.next;
            }
            if(prev == null){
                head = temp;
                temp.next = curr;
            }else{
                prev.next = temp;
                temp.next = curr;
            }
            temp = l2;
        }
        return head;
    }
}
